package leetcode.code0632;

import java.util.List;
import java.util.PriorityQueue;

import leetcode.IDebug;

public class Solution implements IDebug {

	public int[] smallestRange(List<List<Integer>> nums) {
		int max = Integer.MIN_VALUE;
		PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> a[0] - b[0]);
		for (int i = 0; i < nums.size(); i++) {
			int num = nums.get(i).get(0);
			queue.add(new int[] { num, i, 0 });
			max = Math.max(num, max);
		}
		int ans1 = queue.peek()[0], ans2 = max;
		int range = max - ans1;
		while (!queue.isEmpty()) {
			int[] cur = queue.poll();
			int idx = cur[1], next = cur[2] + 1;
			List<Integer> list = nums.get(idx);
			if (list.size() == next) {
				break;
			}
			int num = list.get(next);
			queue.add(new int[] { num, idx, next });
			int min = queue.peek()[0];
			max = Math.max(num, max);
			if (max - min < range) {
				range = max - min;
				ans1 = min;
				ans2 = max;
			}

		}

		return new int[] { ans1, ans2 };
	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
